package org.example.day03;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * <p>  快递公司每日早晨，给每位快递员推送需要送到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最短路径，告诉他最短路径的距离。 </p> <p>  注意： </p> <p>  1.     不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中 </p> <p>  2.     用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过 </p> <p>  3.     所有快递送完后，快递员需回到投递站 </p>
 *
 * 快递公司每日早晨，给每位快递员推送需要送到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最短路径，告诉他最短路径的距离。
 * 注意：
 * 1.     不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中
 * 2.     用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过
 * 3.     所有快递送完后，快递员需回到投递站
 * @date 2024/3/11 15:22
 */
public class test049{

    static final int MAX_CUSTOMERS = 100; // 假设最多有100个客户
    static final int INF = Integer.MAX_VALUE;
    static int[][] distance = new int[MAX_CUSTOMERS + 1][MAX_CUSTOMERS + 1]; // 存储所有顶点对之间的最短路径距离
    static HashMap<Integer, Integer> idToIndex = new HashMap<>(); // 客户ID映射到索引
    static int[] perm = new int[MAX_CUSTOMERS + 1]; // 用于存储排列组合的数组
    static boolean[] visited = new boolean[MAX_CUSTOMERS + 1]; // 记录排列中已经使用过的客户ID
    static int n; // 客户数量

    // 使用Floyd-Warshall算法计算所有顶点对之间的最短路径
    static void floydWarshall(int n) {
        for (int k = 0; k <= n; k++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {
                    if (distance[i][k] != INF && distance[k][j] != INF && distance[i][k] + distance[k][j] < distance[i][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                    }
                }
            }
        }
    }

    // 生成所有排列的递归函数，并计算每种排列的路径长度，返回最短路径长度
    static int findShortestPath(int depth) {
        if (depth == n) {
            // 找到一种排列，计算这种排列的路径长度
            int currDistance = distance[0][perm[0]]; // 从投递站到第一个客户的距离
            for (int i = 0; i < n - 1; i++) {
                currDistance += distance[perm[i]][perm[i + 1]]; // 客户之间的距离
            }
            currDistance += distance[perm[n - 1]][0]; // 从最后一个客户返回投递站的距离
            return currDistance;
        }

        int minDistance = INF;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                perm[depth] = i;
                int currDistance = findShortestPath(depth + 1);
                minDistance = Math.min(minDistance, currDistance);
                visited[i] = false; // 回溯
            }
        }
        return minDistance;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int m = scanner.nextInt();

        // 初始化距离矩阵为INF
        for (int[] row : distance) {
            Arrays.fill(row, INF);
        }
        // 初始化投递站到自己的距离为0
        for (int i = 0; i <= n; i++) {
            distance[i][i] = 0;
        }

        idToIndex.put(0, 0); // 投递站的索引为0
        int index = 1; // 客户的索引从1开始

        // 读取投递站到客户之间的距离
        for (int i = 0; i < n; i++) {
            int custId = scanner.nextInt();
            int dist = scanner.nextInt();
            idToIndex.put(custId, index);
            distance[0][index] = dist;
            distance[index][0] = dist;
            index++;
        }

        // 读取客户之间的距离
        for (int i = 0; i < m; i++) {
            int cust1 = scanner.nextInt();
            int cust2 = scanner.nextInt();
            int dist = scanner.nextInt();
            distance[idToIndex.get(cust1)][idToIndex.get(cust2)] = dist;
            distance[idToIndex.get(cust2)][idToIndex.get(cust1)] = dist;
        }

        // 使用Floyd-Warshall算法计算所有顶点对之间的最短路径
        floydWarshall(n);

        // 初始化访问记录数组
        Arrays.fill(visited, false);

        // 找出所有客户的排列组合中最短的路径长度
        int shortestDistance = findShortestPath(0);

        if (shortestDistance == INF) {
            System.out.println("-1"); // 如果没有有效路径，输出-1
        } else {
            System.out.println(shortestDistance); // 输出最短路径长度
        }

        scanner.close();
    }
}

